#include <bits/stdc++.h>

using namespace std;

const int INF = 1e6;

const int N = 105;
struct Edge
{
    int u, v, w;
}e[10005];

int n, m, cnt;
int pre[N];

void print_path(int s, int t){
    if(s == t){cout<< s<< " ";return;}
    print_path(s, pre[t]);
    cout << t<< " ";
}

void bellman(){
    int s = 1;
    int d[N];
    for(int i = 1; i <= n;i++)d[i] = INF;
    d[s] = 0;
    for(int k = 1; k <= n; k++){
        for(int i =1; i < cnt; i++){
            int x = e[i].u, y = e[i].v;
            if(d[x] > d[y] + e[i].w){
                d[x] = d[y] + e[i];
                pre[x] = y;
            }
        }
    }
    cout << d[n];
}

int main(){
    while(~scanf("%d %d"), &n, &m){
        if(n == 0 && m == 0)return 0;
        cnt = 0;
        while(m --){
            int a, b, c;
            e[cnt].u = a; e[cnt].v = b; e[cnt].w = c; cnt++;
            e[cnt].u = b; e[cnt].v = a; e[cnt].w = c; cnt++;
        }
        bellman();
    }
}